//1.队列-层序遍历（参考树的层序遍历写法）
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr)
            return {};
        vector<int> ret;
        queue<TreeNode*> q;
        
        q.push(root);
        TreeNode* temp;
        while(!q.empty()) {
            int size = q.size();     
            for(int i=0;i<size;++i) {
                temp = q.front(); q.pop();
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);              
            }
            ret.push_back(temp->val);
        }
        return ret;
    }
};
//2.dfs
class Solution {
public:
    void dfs(TreeNode* node, int depth, vector<int>& ret) {
        if(node==nullptr) return;
        if(ret.size()==depth)  //当前层第一次到达，加数字
            ret.push_back(node->val);
        dfs(node->right, depth+1, ret);  //优先访问右子树
        dfs(node->left, depth+1, ret);

        return;
    }

    vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr)
            return {};
        vector<int> ret;
        dfs(root, 0, ret);
       
        return ret;
    }
};